Catalan's problem

In mathematics, Catalan's problem asks the number of ways n + 1 factors can be completely parenthesized by n pairs of parentheses. For example, the following are the 14 ways that 5 factors can be parenthesized:

• (1 (2 (3 (4 5))))
• (1 (2 ((3 4) 5)))
• (1 ((2 3) (4 5)))
• (1 ((2 (3 4)) 5))
• (1 (((2 3) 4) 5))
• ((1 2) (3 (4 5)))
• ((1 2) ((3 4) 5))
• ((1 (2 3)) (4 5))
• ((1 (2 (3 4))) 5)
• ((1 ((2 3) 4)) 5)
• (((1 2) 3) (4 5))
• (((1 2) (3 4)) 5)
• (((1 (2 3)) 4) 5)
• ((((1 2) 3) 4) 5)

The numbers of ways of performing these pairings are the Catalan numbers.

See also

• Catalan number
• Eugène Charles Catalan

References

• Gardner, Martin (1988). Time Travel and Other Mathematical Bewilderments. New York: W.H. Freeman and Company. pp. p. 256. ISBN 0-7167-1924-X. 
• Weisstein, Eric W., "Catalan's Problem" from MathWorld.